package com.lfg.leetcode.leetcode0;


import java.util.ArrayList;
import java.util.List;

public class No51solveNQueens {

    public static void main(String[] args) {
        List<List<String>> ret = solveNQueens(4);
        System.out.println(ret);
    }

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> ret = new ArrayList<>();
        int[] y = new int[n];
        solveNQueens(n, ret, y, 0);
        return ret;
    }

    public static void solveNQueens(int n, List<List<String>> ret, int[] y, int rowNo) {
        if (rowNo == n) {
            List<String> l = new ArrayList<String>();
            for (int i = 0; i < rowNo; i++) {
                int i2 = y[i];
                StringBuilder sb = new StringBuilder(n);
                for (int j = 0; j < n; j++) {
                    if (i2 == j) {
                        sb.append('Q');
                    } else {
                        sb.append('.');
                    }
                }
                l.add(sb.toString());
            }
            ret.add(l);
            return;
        }
        for (int j = 0; j < n; j++) {
            boolean flag = true;
            for (int i = 0; i < rowNo; i++) {
                int ey = y[i];
                if (ey == j) {
                    flag = false;
                    break;
                }
                if (i - rowNo == j - ey || i - ey == rowNo - j) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                y[rowNo] = j;
                solveNQueens(n, ret, y, rowNo + 1);
            }
        }
    }
}

